package 算法模板;

import java.util.Arrays;

/**
 * 概念:
 * 线段树是一颗二叉树
 * 如果当前节点的索引为 i ，那么它的左子节点索引为 i*2 ，右子节点索引为 i*2+1
 * <p>
 * 线段树的节点数量:
 * 数组数量为 n ，最坏情况，线段树需要 4*n 的节点数量
 * <p>
 * 使用场景:
 * 1，单点修改-区间查询(最小值，最大值，总和)
 * 2，区间修改-单点查询
 */
public class 线段树 {

    public static void main(String[] args) {

        int[] nums = {4, 3, 2, 1};
        SegmentTree segmentTree = new SegmentTree(nums);
        System.out.println(Arrays.toString(segmentTree.tree));
        System.out.println(segmentTree.sum(0, 3));
        segmentTree.add(2, -1);
        System.out.println(segmentTree.sum(0, 3));

    }

}

class SegmentTree {

    Node[] tree;

    int[] nums;

    public SegmentTree(int[] nums) {
        this.nums = nums;
        tree = new Node[nums.length * 4];
        build(0, nums.length - 1);
    }

    // 往索引 targetIdx 的位置增加 num
    public void add(int targetIdx, int num) {
        add(1, targetIdx, num);
    }

    // 思路:
    // 从根节点一直往下找，找出包含 targetIdx 的所有区间
    // 直至找到 tree[index].left == tree[index].right == targetIdx 的叶子节点
    // 从下往上更新，区间和
    private void add(int index, int targetIdx, int num) {
        if (tree[index].left == tree[index].right) {
            tree[index].sum += num;
            return;
        }
        // 目标节点索引小于等于左子节点的右边界，说明目标节点在左子节点的区间里面
        if (targetIdx <= tree[index * 2].right) {
            add(index * 2, targetIdx, num);
        } else {
            add(index * 2 + 1, targetIdx, num);
        }
        tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum;
    }

    public int sum(int left, int right) {
        return sum(1, left, right);
    }

    private int sum(int index, int left, int right) {
        // 当前节点区间全部包含在目标区间里面
        if (left <= tree[index].left && tree[index].right <= right) {
            return tree[index].sum;
        }
        // 当前节点区间和目标区间没有交集
        if (tree[index].right < left || tree[index].left > right) return 0;
        int sum = 0;
        // 右子节点区间和目前区间有交集
        if (tree[index * 2 + 1].left <= right) {
            sum += sum(index * 2 + 1, left, right);
        }
        // 左子节点区间和目前区间有交集
        if (tree[index * 2].right >= left) {
            sum += sum(index * 2, left, right);
        }
        return sum;
    }

    private void build(int left, int right) {
        build(1, left, right);
    }

    private void build(int index, int left, int right) {
        tree[index] = new Node();
        tree[index].left = left;
        tree[index].right = right;
        if (left == right) {  // 最后一层，只有一个节点
            tree[index].sum = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        // 分别构造左子树和右子树
        build(index * 2, left, mid);
        build(index * 2 + 1, mid + 1, right);
        tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum;
    }

    class Node {
        // 左边界
        private int left;
        // 右边界
        private int right;
        // [左边界,右边界] 的总和
        private int sum;

        @Override
        public String toString() {
            return "Node{" +
                    "l=" + left +
                    ", r=" + right +
                    ", sum=" + sum +
                    '}';
        }
    }

}

/**
 * 区间修改，查询区间最大值
 */
class SegmentTree2 {
    private int[] tree;       // 线段树
    private int[] lazy;       // 懒标记数组
    private int n;

    // 构造函数，初始化线段树和懒标记数组
    public SegmentTree2(int size) {
        this.n = size;
        this.tree = new int[4 * n];  // 线段树大小
        this.lazy = new int[4 * n];  // 懒标记数组大小
    }

    // 传播懒标记
    private void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node];  // 更新当前节点的值

            // 如果不是叶节点，传递懒标记到左右子节点
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }

            // 清空当前节点的懒标记
            lazy[node] = 0;
        }
    }

    // 区间更新
    public void update(int l, int r, int value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区间更新的递归实现
    private void updateRange(int node, int start, int end, int l, int r, int value) {
        pushDown(node, start, end);

        if (start > end || start > r || end < l) return;  // 当前区间不相关

        if (start >= l && end <= r) {  // 当前区间完全在更新范围内
            lazy[node] += value;  // 标记懒更新
            pushDown(node, start, end);  // 更新当前节点的值
            return;
        }

        // 否则继续递归更新左右子树
        int mid = (start + end) / 2;
        updateRange(2 * node, start, mid, l, r, value);
        updateRange(2 * node + 1, mid + 1, end, l, r, value);

        // 更新当前节点
        tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
    }

    // 区间查询
    public int query(int l, int r) {
        return queryMax(1, 0, n - 1, l, r);
    }

    // 区间查询的递归实现
    private int queryMax(int node, int start, int end, int l, int r) {
        pushDown(node, start, end);

        if (start > end || start > r || end < l) return Integer.MIN_VALUE;  // 当前区间不相关

        if (start >= l && end <= r) return tree[node];  // 当前区间完全在查询范围内

        int mid = (start + end) / 2;
        int leftMax = queryMax(2 * node, start, mid, l, r);
        int rightMax = queryMax(2 * node + 1, mid + 1, end, l, r);

        return Math.max(leftMax, rightMax);  // 返回左右子树的最大值
    }

}